/*
 * @lc app=leetcode.cn id=1514 lang=cpp
 *
 * [1514] 概率最大的路径
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<double, int>>> graph(n);
        for (int i = 0; i < edges.size(); i++) {
            auto& e = edges[i];
            graph[e[0]].emplace_back(succProb[i], e[1]);
            graph[e[1]].emplace_back(succProb[i], e[0]);
        }

        // 用priority_queue贪
        priority_queue<pair<double, int>> que;
        vector<double> probDP(n, 0);

        que.emplace(1, start);
        probDP[start] = 1;
        while (!que.empty()) {
            auto [prob, nodeCurrentIndex] = que.top();
            que.pop();

            // // 只是计算从起点 start 到某一个终点 end 的最短路径
            // // 判断当前 最近/概率最大 node 已经是end即可返回
            // if (nodeCurrentIndex == end) {
            //     return prob;
            // }
            // // 但实际上为啥反而变慢了呢

            if (prob < probDP[nodeCurrentIndex]) {
                continue;
            }
            // while 循环每执行一次，都会往外拿一个元素
            // 但想往队列里放元素，有很多限制
            
            // 不需要使用原始版的visit~
            for (auto& [prNext, nodeNextIndex] : graph[nodeCurrentIndex]) {
                if (probDP[nodeNextIndex] < probDP[nodeCurrentIndex] * prNext) {
                    probDP[nodeNextIndex] = probDP[nodeCurrentIndex] * prNext;
                    que.emplace(probDP[nodeNextIndex], nodeNextIndex);
                }
            }
        }
        return probDP[end];
    }
};
// @lc code=end


class SolutionWithoutOptimization {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        // neighbor list
        neighbors_.resize(n);
        for (int i=0;i<edges.size();++i) {
            int a = edges[i][0];
            int b = edges[i][1];
            double prob = succProb[i];

            neighbors_[a][b] = prob;
            neighbors_[b][a] = prob;
        }

        config_.resize(n, 0);
        DP_.resize(n, -1.0);

        // init start
        config_[start] = 1;
        DP_[start] = 1.0;
        for (auto& ticket : neighbors_[start]) {
            int to = ticket.first;
            double prob = ticket.second;
            DP_[to] = prob;
        }

        // dijkstra
        for (int i=1;i<n;++i) {
            // 普通的 Dijkstra 算法是通过枚举来寻找
            // 「未确定节点」中与起点距离最近的点 O(edge*node)
            // 可以使用优先队列优化这一过程 O(edge*log(edge))
            double maxPorb = 0.0;
            int maxProbId = -1;
            for (int j=0;j<n;++j) {
                if (config_[j] == 1) {continue;}
                
                // init prob -1 no need to check
                if (DP_[j] > maxPorb) {
                    maxPorb = DP_[j];
                    maxProbId = j;
                }
            }

            if (maxProbId < 0) {continue;}

            config_[maxProbId] = 1;

            for (auto& ticket : neighbors_[maxProbId]) {
                int to = ticket.first;
                double prob = ticket.second;
                if (config_[to] == 1) {continue;}

                double newProb = maxPorb * prob;
                if (newProb > DP_[to]) {
                    DP_[to] = newProb;
                }
            }
        }

        double result = DP_[end];
        return result > 0 ? result : 0.0;
    }
private:
    // index : from , <key : to, value : prob>
    std::vector<std::map<int, double>> neighbors_;
    std::vector<int> config_;
    std::vector<double> DP_;
};

int main() {
    int n = 3;
    vector<vector<int>> edges = {
        {0,1},
        // {1,2},
        // {0,2}
    };
    vector<double> succProb = {0.5,
    // 0.5,0.2
    };
    int start = 0;
    int end = 2;

    Solution test;
    test.maxProbability(n, edges, succProb, start, end);
}

// 3\n[[0,1],[1,2],[0,2]]\n[0.5,0.5,0.3]\n0\n2

// 3\n[[0,1]]\n[0.5]\n0\n2
